package arr


/*
时间复杂度:O(N)
空间复杂度:O(1)
*/
func pivotIndex(nums []int) int {
	// 前缀和可以在遍历第一遍的时候求出当前元素的前缀和，而不必保存到新的切片中
	// 如果存在位置i，使得nums[0~i-1] 和nums[i+1~]的和相等，则2*nums[0~i-1]+nums[i]==nums[0~n-1]
	total := 0
	for _, v := range nums {
		total += v
	}
	sum := 0
	for i, v := range nums {
		if 2*sum + v == total {
			return i
		}
		sum += v
	}
	return -1
}


/*
时间复杂度:O(N)
空间复杂度:O(N)
 */
func pivotIndex1(nums []int) int {
	n := len(nums) + 2
	preSum := make([]int, n)
	for i := 1; i < n-1; i++ {
		preSum[i] += preSum[i-1] + nums[i-1]
	}
	preSum[n-1] = preSum[n-2]
	result := -1
	for i := 1; i < n-1; i++ {
		if preSum[i-1] == preSum[n-1]-preSum[i] {
			result = i
		}
	}
	return result
}
